package org.example.myleet.p645;

import java.util.Arrays;

public class Solution {
    /**
     * 空间换时间版本，O(n)
     */
    public int[] findErrorNums(int[] nums) {
        int[] result = new int[2];
        boolean[] existence = new boolean[nums.length + 1];
        for (int i = 0; i < nums.length; ++i) {
            if (existence[nums[i]]) {
                result[0] = nums[i];
            } else {
                existence[nums[i]] = true;
            }
        }
        for (int i = 1; i < existence.length; ++i) {
            if (!existence[i]) {
                result[1] = i;
            }
        }
        return result;
    }

    /**
     * 时间换空间版本，O(n + n*log(n))
     */
//    public int[] findErrorNums(int[] nums) {
//        int[] result = new int[2];
//        Arrays.sort(nums);
//        int repeatIdx = 0;
//        for (int i = 0; i < nums.length - 1; ++i) {
//            if (nums[i] == nums[i + 1]) {
//                result[0] = nums[i];
//                repeatIdx = i;
//                break;
//            }
//        }
//        int seq = 0;
//        for (int i = 0; i < nums.length; ++i) {
//            ++seq;
//            if (i < repeatIdx) {
//                if (nums[i] != seq) {
//                    result[1] = seq;
//                    break;
//                }
//            } else if (i > repeatIdx) {
//                if (nums[i] != seq - 1) {
//                    result[1] = seq - 1;
//                    break;
//                }
//            }
//        }
//        if (result[1] == 0) {
//            result[1] = nums.length;
//        }
//        return result;
//    }
}
